package queue;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * 使用数组模拟一个简单环形队列
 * 队列是一种FIFO的模型 即先入先出
 * 通过首尾指针+数组实现
 * 增加数据时上移头指针，获取数据时上移尾指针
 * 环形队列则将移动指针的方法从++改为 （指针+1）% 最大容量
 */

class Queue_Test{
    public static void main(String[] args) {
        Queue queue = new Queue(4);
        queue.add("1");
        queue.add("2");
        System.out.println(queue.peek());
        System.out.println(queue.get());


    }
}

public class Queue {
    // 用来模拟队列的数组
    private static Object[] value = null;
    // 扩容因子
    private static float DEFAULT_LOAD_FACTOR = 0.75f;
    // 初始容量
    private static int DEFAULT_SIZE_FACTOR = 4<<2;
    // 扩容倍数
    private static float DEFAULT_MORE_SIZE = 1.5f;
    // 元素个数
    private static int size;
    // 底部指针
    private static int rear;
    // 头部指针
    private static int front;

    /**
     * 无参构造 直接采用默认的参数创建一个数组
     */
    public Queue() {
        value = new Object[DEFAULT_SIZE_FACTOR];
        front = 0;
        rear = 0;
    }

    /**
     *
     * @param LOAD_FACTOR 扩容因子
     */
    public Queue(float LOAD_FACTOR) {
        value = new Object[DEFAULT_SIZE_FACTOR];
        DEFAULT_LOAD_FACTOR = LOAD_FACTOR;
        front = 0;
        rear = 0;
    }

    /**
     *
     * @param SIZE_FACTOR 初始容量
     */
    public Queue(int SIZE_FACTOR) {
        value = new Object[SIZE_FACTOR];
        DEFAULT_SIZE_FACTOR= SIZE_FACTOR;
        front = 0;
        rear = 0;
    }

    /**
     *
     * @param SIZE_FACTOR 初始容量
     * @param LOAD_FACTOR 扩容因子
     * @param MORE_SIZE   扩容倍数
     */
    public Queue(int SIZE_FACTOR ,float LOAD_FACTOR , float MORE_SIZE ) {
        value = new Object[SIZE_FACTOR];
        DEFAULT_SIZE_FACTOR= SIZE_FACTOR;
        DEFAULT_LOAD_FACTOR = LOAD_FACTOR;
        DEFAULT_MORE_SIZE = MORE_SIZE;
        front = 0;
        rear = 0;
    }

    //判读有没有满 满则自动扩容
    private final Boolean isFull(){
        // 判断 元素个数 有没有到达 默认个数 * 扩容因子
        if (size == DEFAULT_SIZE_FACTOR*DEFAULT_LOAD_FACTOR){
            // 获取扩容后的个数，并且重新创建一个新的数组
            int new_Size = (int) (DEFAULT_SIZE_FACTOR*DEFAULT_MORE_SIZE);
            Object[] new_value = new Object[new_Size];
            // 数据进行重新赋值
            for (int i = 0; i < DEFAULT_SIZE_FACTOR; i++) {
                new_value[i] = value[i];
            }
            // 数组指向新数组
            value = new_value;
            DEFAULT_SIZE_FACTOR = new_Size;
        }
        return (front + 1) % DEFAULT_SIZE_FACTOR == rear;
    }
    //判断是否为空
    private final Boolean isEmpty(){
        // 头尾指针相同则代表队列为空
        return rear==front;
    }

    // 数据添加
    public final void add(Object v){
        // 先进行是否满判断
        isFull();
        // 将头指针所在的数组赋值
        value[front] = v;
        size ++;
        // 头指针后移 ，由于是环形链表 需要用此公式
        front = (front+1)%DEFAULT_SIZE_FACTOR;
    }

    // 获取数据
    public final Object get(){
        Object peek = peek();
        size --;
        rear = (rear+1)%DEFAULT_SIZE_FACTOR;
        return peek;
    }

    // 获取数据(不移动指针)
    public final Object peek(){
        if (isEmpty()) throw new RuntimeException("队列为空");
        Object v = value[rear];
        return v;
    }

    // 获取长度
    public int length(){ return size; }

    // 获取总长度
    public int size(){return DEFAULT_SIZE_FACTOR;}
}
